package codetop.microsoft.T210;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: 18362
 * @Create: 2022-08-17 11:41:09 星期三
 */
class Solution {

    private List<Integer>[] graph;
    private int[] pre;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        graph = new List[numCourses];
        for (int i=0; i<numCourses; ++i)
            graph[i] = new ArrayList<>();
        pre = new int[numCourses];
        for (int i=0; i<prerequisites.length; ++i) {
            int u = prerequisites[i][0], v = prerequisites[i][1];
            graph[v].add(u);
            pre[u]++;
        }

        int[] res = new int[numCourses];
        int k = 0;
        Deque<Integer> dq = new LinkedList<>();
        for (int i=0; i<pre.length; ++i) {
            if (pre[i] == 0)
                dq.offer(i);
        }
        while (!dq.isEmpty()) {
            int v = dq.poll();
            res[k++] = v;
            for (int i=0; i<graph[v].size(); ++i) {
                int u = graph[v].get(i);
                pre[u]--;
                if (pre[u] == 0)
                    dq.offer(u);
            }
        }
        if (k == numCourses)
            return res;
        return new int[]{};
    }
}